package tree;

import java.util.*;
import java.util.List;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/7f17yi/
public class 彩灯装饰记录3 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //层序遍历 + 双端队列
    class Solution {
        public List<List<Integer>> decorateRecord(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root != null) queue.add(root);
            while (!queue.isEmpty()){
                LinkedList<Integer> tmp = new LinkedList<>();

                for(int i=queue.size(); i>0; i--){
                    TreeNode node = queue.poll();
                    if(res.size()%2 == 0)
                        tmp.addLast(node.val);
                    else
                        tmp.addFirst(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right!= null) queue.add(node.right);
                }
                res.add(tmp);
            }
            return res;
        }
    }
    //层序遍历 + 双端队列（奇偶层逻辑分离）
    class Solution2 {
        public List<List<Integer>> decorateRecord(TreeNode root) {
            Deque<TreeNode> deque = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root != null) deque.add(root);
            while(!deque.isEmpty()) {
                // 打印奇数层
                List<Integer> tmp = new ArrayList<>();
                for(int i = deque.size(); i > 0; i--) {
                    // 从左向右打印
                    TreeNode node = deque.removeFirst();
                    tmp.add(node.val);
                    // 先左后右加入下层节点
                    if(node.left != null) deque.addLast(node.left);
                    if(node.right != null) deque.addLast(node.right);
                }
                res.add(tmp);
                if(deque.isEmpty()) break; // 若为空则提前跳出
                // 打印偶数层
                tmp = new ArrayList<>();
                for(int i = deque.size(); i > 0; i--) {
                    // 从右向左打印
                    TreeNode node = deque.removeLast();
                    tmp.add(node.val);
                    // 先右后左加入下层节点
                    if(node.right != null) deque.addFirst(node.right);
                    if(node.left != null) deque.addFirst(node.left);
                }
                res.add(tmp);
            }
            return res;
        }
    }
    //层序遍历 + 倒序
    class Solution3 {
        public List<List<Integer>> decorateRecord(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root != null) queue.add(root);
            while(!queue.isEmpty()) {
                List<Integer> tmp = new ArrayList<>();
                for(int i = queue.size(); i > 0; i--) {
                    TreeNode node = queue.poll();
                    tmp.add(node.val);
                    if(node.left != null) queue.add(node.left);
                    if(node.right != null) queue.add(node.right);
                }
                if(res.size()%2 == 1) Collections.reverse(tmp);
                res.add(tmp);
            }
            return res;
        }
    }
}
/*
Collections 是 Java 中一个非常实用的工具类，它提供了许多静态方法来操作集合（如 List, Set, Map 等）。
这些方法可以帮助简化集合的操作，提高代码的可读性和效率。
常用方法
以下是一些常用的 Collections 类的方法及其用途：
reverse(List list)：
将列表中的元素反转。
例如：Collections.reverse(list);
shuffle(List list)：
打乱列表中元素的顺序。
例如：Collections.shuffle(list);
sort(List list)：
对列表进行排序。
例如：Collections.sort(list);
sort(List list, Comparator c)：
根据指定的比较器对列表进行排序。
例如：Collections.sort(list, Comparator.comparingInt(Integer::intValue));
max(Collection col)：
返回集合中的最大值。
例如：Collections.max(list);
min(Collection col)：
返回集合中的最小值。
例如：Collections.min(list);
fill(List list, Object value)：
将列表中的所有元素设置为指定值。
例如：Collections.fill(list, 0);
swap(List list, int i, int j)：
交换列表中两个位置的元素。
例如：Collections.swap(list, 0, 1);
synchronizedList(List list)：
创建一个线程安全的列表。
例如：List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());
unmodifiableList(List list)：
创建一个不可修改的列表。
例如：List<Integer> unmodifiableList = Collections.unmodifiableList(list);
 */